Longest Valid Parentheses

问题描述

Given a string containing just the characters ( and ), find the length of the longest valid (well-formed) parentheses substring.

For ((), the longest valid parentheses substring is (), which has length = 2.

Another example is )()()), where the longest valid parentheses substring is ()(), which has length = 4.

---

思路

这题我的想法是用一个栈来辅助判断，括号匹配，然而怎么写都有问题，百思不得其解，(:зゝ∠)最后参考了一份非常优雅的代码，转来学习。

---

优雅的代码

其中的start下标和将下标压入栈的方法，十分值得学习，代码太优雅了！看到了自己的差距。

int longestValidParentheses(string s) {
       int res = 0, start = 0;
        stack<int> l;
        for (int i =0; i <= s.size(); ++i) {
            if ( s[i] == '(' ) l.push(i);
            else if ( s[i] == ')' ) {
                if (l.empty()) start = i + 1;
                else {
                    l.pop();
                    res = l.empty() ? max(res, i - start + 1) : max(res, i - l.top());
                }
            }
        }
        return res;
        
}

---

题外话

说到优雅的代码，我又想起了另外一道题，题目大致如下：

给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。
比如当 x=5，k=1时返回 2，因为5+1=6 不等于 5|1=5，而 5+2=7 等于 5 | 2 = 7。即返回第k小且满足等式的y。

优雅的代码

#include <iostream>
#include <string>

using namespace std;

int main()
{
    long long x, k;
    cin>>x>>k;
    long long bitNum = 1;
    long long ans = 0;
    while(k)
    {
        if((x & bitNum) == 0)
        {
            ans += (bitNum * (k & 1));
            k >>= 1;
        }
        bitNum <<= 1;
    }
    cout<<ans<<endl;
    system("pause");
    return 0;
}

总结

短短几行代码，体现了一个人精妙的思维，希望自己以后也能写出如此的代码！